import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2020/3/1 上午 10:13
 */
public class month2003 {

    class contest178 {

        public int[] smallerNumbersThanCurrent(int[] nums) {
            int[] ret = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                int count = 0;
                for (int num : nums) {
                    if (num < nums[i]) {
                        count++;
                    }
                }
                ret[i] = count;
            }
            return ret;
        }

        public String rankTeams(String[] votes) {
            int n = votes[0].length();
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                map.put(votes[0].charAt(i), i);
            }
            int[][] voteCnt = new int[n][n + 1];
            for (int i = 0; i < n; i++) {
                voteCnt[i][n] = i;
            }
            for (String vote : votes) {
                for (int i = 0; i < n; i++) {
                    voteCnt[map.get(vote.charAt(i))][i]++;
                }
            }
            Arrays.sort(voteCnt, (a, b) -> {
                for (int i = 0; i < n; i++) {
                    if (a[i] != b[i]) {
                        return b[i] - a[i];
                    }
                }
                return votes[0].charAt(a[n]) - votes[0].charAt(b[n]);
            });
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(votes[0].charAt(voteCnt[i][n]));
            }
            return sb.toString();
        }

        public boolean isSubPath(ListNode head, TreeNode root) {
            if (root == null) {
                return false;
            }
            if (head.val == root.val) {
                if (helper(head.next, root.left) || helper(head.next, root.right)) {
                    return true;
                }
            }
            return isSubPath(head, root.left) || isSubPath(head, root.right);
        }

        private boolean helper(ListNode next, TreeNode root) {
            if (next == null) {
                return true;
            }
            if (root == null) {
                return false;
            }
            if (next.val == root.val) {
                if (helper(next.next, root.left)) {
                    return true;
                }
                return helper(next.next, root.right);
            } else {
                return false;
            }
        }

        public int minCost(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[][] visited = new int[m][n];
            for (int i = 0; i < visited.length; i++) {
                Arrays.fill(visited[i], Integer.MAX_VALUE);
            }
            PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
            queue.offer(new int[]{0, 0, 0});
            visited[0][0] = 0;
            while (!queue.isEmpty()) {
                int[] top = queue.poll();
                int cost = top[0];
                int i = top[1];
                int j = top[2];
                if ((i == m - 1) && (j == n - 1)) {
                    return cost;
                }
                int[][] offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
                int d = grid[i][j];
                for (int k = 0; k < 4; k++) {
                    int ii = i + offsets[k][0];
                    int jj = j + offsets[k][1];
                    int nCost = cost + ((k + 1 == d) ? 0 : 1);
                    if (ii < 0 || ii >= m || jj < 0 || jj >= n || visited[ii][jj] <= nCost) {
                        continue;
                    }
                    visited[ii][jj] = nCost;
                    queue.offer(new int[]{nCost, ii, jj});
                }
            }
            return Integer.MAX_VALUE;
        }

    }

    public static void main(String[] args) {

    }

}
